import sun.reflect.generics.tree.Tree;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class BSTIterator {
    LinkedList<Integer> list;
    int index=0;
    public BSTIterator(TreeNode root) {
        list=new LinkedList<>();
        index=0;
        addData(root);
    }

    public int next() {
        return list.get(index++);
    }

    public boolean hasNext() {
        return index<list.size();
    }
    public void addData(TreeNode root){
        if(root==null){
            return;
        }
        addData(root.left);
        list.add(root.val);
        addData(root.right);
    }
}


class Solution {

    public int wateringPlants(int[] plants, int capacity) {
        int len = plants.length;
        int sum = 0;
        int water = capacity;
        for (int i = 0; i < len; i++) {
            if (water >= plants[i]) {
                sum++;
            } else {
                water = capacity;
                sum += i * 2 + 1;
            }
            water -= plants[i];
        }
        return sum;
    }












    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> list = new ArrayList<>();
        if (n == 1) {
            list.add(new TreeNode(0));
            return list;
        }
        for (int i = 1; i < n - 1; i += 2) {
            List<TreeNode> listTree = allPossibleFBT(i);
            List<TreeNode> rightTree = allPossibleFBT(n - i - 1);
            for (int left = 0; left < listTree.size(); left++) {
                for (int right = 0; right < rightTree.size(); right++) {
                    TreeNode node = new TreeNode(0);
                    node.left = listTree.get(left);
                    node.right = rightTree.get(right);
                    list.add(node);
                }
            }
        }
        return list;
    }
}









public class project {
    public void rotate(int[][] matrix) {
        int len=matrix.length;
        for(int i=0;i<matrix.length/2;i++) {
            for (int j = 0; j < (matrix.length+1)/2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
                matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = tmp;
            }
        }
    }


























    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int row=rowSum.length;
        int col=colSum.length;
        int[][] arr=new int[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                arr[i][j]=Math.min(rowSum[i],colSum[j]);
                rowSum[i]-=arr[i][j];
                colSum[j]-=arr[i][j];
            }
        }
        return arr;
    }



















    public int minimumTotal(List<List<Integer>> triangle) {
        int row=triangle.size();
        int[] dp=new int[row];
        for(int i=0;i<row;i++){
            for(int j=i;j>=0;j--){
                if(i!=0&&i==j){
                    dp[j]=dp[j-1];
                }else if(j!=0){
                    dp[j]=Math.min(dp[j],dp[j-1]);
                }
                dp[j]+=triangle.get(i).get(j);
            }
        }
        return Arrays.stream(dp).min().getAsInt();
    }



















    public int minimumTotal1(List<List<Integer>> triangle) {
        int row=triangle.size();
        int[] dp=new int[row];
        for(int i=0;i<row;i++){
            for(int j=i;j>=0;j--){
                if(i!=0&&i==j){
                    dp[j]=dp[j-1];
                }else if(j!=0){
                    dp[j]=Math.min(dp[j],dp[j-1]);
                }
                dp[j]+=triangle.get(i).get(j);
            }
        }
        return Arrays.stream(dp).min().getAsInt();
    }













    public int[][] generateMatrix(int n) {
        int[][] arr=new int[n][n];
        int leftUp=0;
        int rightUP=n-1;
        int leftFall=0;
        int rightFall=n-1;
        int index=1;
        while (leftUp<=rightUP&&leftFall<=rightFall){
            for(int i=leftUp;i<=rightUP;i++){
                arr[leftFall][i]=index++;
            }
            for(int i=leftFall+1;i<=rightFall;i++){
                arr[i][rightUP]=index++;
            }
            if(leftUp<rightUP&&leftFall<rightFall){
                for(int i=rightUP-1;i>leftUp;i--){
                    arr[rightFall][i]=index++;
                }
                for(int i=rightFall;i>leftFall;i--){
                    arr[i][leftUp]=index++;
                }
            }
            leftUp++;
            leftFall++;
            rightFall--;
            rightUP--;
        }
        return arr;
    }














    public int mostWordsFound(String[] sentences) {
        int max=0;
        for(String s : sentences){
            String[] str=s.split(" ");
            max=Math.max(max, str.length);
        }
        return max;
    }












    public String[] findOcurrences(String text, String first, String second) {
        List<String> list=new ArrayList<>();
        String[] str=text.split(" ");
        for(int i=0;i<str.length-2;i++){
            if(str[i].equals(first)&&str[i+1].equals(second)){
                list.add(str[i+2]);
            }
        }
        return list.toArray(new String[list.size()]);
    }
}
